Many modern software applications display three-dimensional representations of objects and scenes as part of a user interface. Three-dimensional (3D) graphics are used in a wide range of applications including video games, simulations, virtual reality applications, geospatial information applications, and applications for mapping and navigation. In many applications, 3D graphics are more useful than two-dimensional (2D) graphics at depicting real-world environments and locations because the normal interaction between humans and the real-world occurs in three dimensions. The 3D graphics are typically generated with multiple polygons that form the shapes of objects and other structures in a 3D virtual environment. Modern 3D graphics also include numerous graphical effects including, but not limited to, lighting effects, texturing, and shadow effects that a processor applies to the polygons to display the 3D environment. Modern processors use both central processing units (CPUs) and graphical processing units (GPUs) as hardware that performs the processing required to execute software programs that implement a 3D application programming interface (API), with OpenGL, OpenGL ES, Vulkan, Metal, and different versions of Direct 3D being examples of APIs that are commonly used in the art.
Many 3D hardware and software applications generate graphics of shadows to provide 3D perception for objects visualized in 3D scenes. Existing techniques for shadow effects simulation including shadow volumes, and shadow maps that generate shadow effects with varying degrees of realism. However, these prior art methods are computationally intensive and are often not suitable for low power embedded devices. Another prior art solution for soft shadow effects simulation on embedded devices generates high quality real-time soft shadow effects with reduced memory utilization through the generation of shadow polygons around objects in the 3D environment, such as building. However, this prior art method only works for 3D objects with convex footprints. For example, FIG. 7 depicts the prior art shadow generation system that produces an accurate shadow 704 along a wall of a convex building model 702, but produces inaccurate shadows that cover a courtyard and other outdoor regions 708 around a building model 706 that is formed with a concave structure. The term “concave” refers to an object with one or more vertices that are located within a convex perimeter polygon forms a “footprint” around the base of the object at ground level in a 3D virtual environment. A processor generates the convex footprint polygon using a convex hull or other suitable convex perimeter process. The concave structure leads to the graphical artifacts depicted in FIG. 7 where a ground shadow or light effect is improperly applied to regions of the convex footprint for the object that lie outside of some concave exterior surfaces of the object. The generated shadows in the prior art techniques also have no relation with the position of a light source in the 3D virtual environment, such as the position of the sun in a 3D virtual environment that depicts a geographic region in a mapping and navigation application program. Consequently, improved techniques for rendering accurate shadows in 3D scenes for concave objects and for adjusting shadows based on the positions of light sources in an efficient manner would be beneficial.